package algorithm_demo.demo05;

import java.util.*;

/**
 * N皇后问题
 *
 * @author Api
 * @date 2023/3/7 22:09
 */
public class Code08_NQueens {

    /*
        N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行，不同列，也不在同一条斜线上
        给定一个整数n，返回n皇后的摆法有多少种。
        n=1，返回1
        n=2或3,2皇后和3皇后问题无论怎么摆都不行，返回0
        n=8，返回92
    */
    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return process1(0, record, n);
    }

    /*
     * 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不同斜线
     * 目前来到了第i行
     * record[0..i-1]表示之前的行，放了的皇后位置
     * n代表整体一共有多少行，0-n-1行
     * 返回值是，摆完所有的皇后，合理的摆法有多少种
     */
    public static int process1(int i, int[] record, int n) {
        if (i == n) {//base case
            return 1;
        }
        //没有到终止位置，还有皇后要摆
        int res = 0;
        for (int j = 0; j < n; j++) {//当前行在i行，尝试i行所有的列 ->j
            //当前i行的皇后，放在j列，会不会和之前（0..i-1）的皇后，不共行共列或者共斜线
            //如果是，认为有效
            //如果不是，认为无效
            if (isValid(record, i, j)) {
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            //Math.abs(record[k]-j)==Math.abs(i-k)  这个就是判断 是否斜线
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    /*优化*/
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        //如果你是13皇后问题，limit最右13个1，其他都是0
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    /**
     * 递归函数
     * & ：如果上下同为0则为0，如果一个为1，一个为0则为0，如果同时为1则为1.
     * | ：如果一个为1，一个为0，则结果为1，如果都是1则为1
     * @param limit       划定了问题的规模->固定不变的
     * @param colLimit    列的限制，1的位置不能放皇后，0的位置可以
     * @param leftDiaLim  左斜线的限制，1的位置不能放皇后，0的位置可以
     * @param rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
     * @return
     */
    public static int process2(int limit, int colLimit, int leftDiaLim, int rightDiaLim) {
        if (colLimit == limit) {//base case
            return 1;
        }
        //limit: 比如8皇后  则为 0000 0000 | 1111 1111
        //limit     9皇后  则为 0 0000 0000 | 1 1111 1111 固定不变
        // colLimit | leftDiaLim | rightDiaLim 表示总限制，（~(colLimit | leftDiaLim | rightDiaLim) 取反表示可以放皇后的位置）
        // 但是前面的 0000 0000 此时也变成1，则通过limit按位与，则 比如0000 0000 | 1101 1000，这里的1表示可以放皇后的位置

        //所有候选皇后的位置，都在pos上
        //colLimit | leftDiaLim | rightDiaLim  代表总限制
        int pos = limit & (~(colLimit | leftDiaLim | rightDiaLim));
        int mostRightOne;
        int res = 0;
        // pos中的1表示可以放皇后的位置
        while (pos != 0) {
            //每次提取最右侧的1来，比如：0 1 0 1 1 0 0 0  -> 0 0 0 0 1 0 0 0  (公式：a&(~a +1))
            mostRightOne = pos & (~pos + 1);
            //这里是提取出下一个1，（0 1 0 1 1 0 0 0） - （0 0 0 0 1 0 0 0）=0 1 0 1 0 0 0 0  -> pos & (~pos + 1) 则为 0 0 0 1 0 0 0 0
            //这里是提取出下一个1，0 1 0 1 1 0 0 0  -> 0 1 0 0 0 0 0 0
            pos = pos - mostRightOne;
            res += process2(limit, colLimit | mostRightOne,
                (leftDiaLim | mostRightOne) << 1,
                (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }


    /*
    *   回溯三部曲
        按照我总结的如下回溯模板，我们来依次分析：
        void backtracking(参数) {
            if (终止条件) {
                存放结果;
                return;
            }
            for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
                处理节点;
                backtracking(路径，选择列表); // 递归
                回溯，撤销处理结果
            }
        }
    *
    * https://leetcode.cn/problems/n-queens/
    * */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queues = new int[n];
        Arrays.fill(queues, -1);
        Set<Integer> cols = new HashSet<>();//列集，记录出现过皇后的列
        Set<Integer> diag1 = new HashSet<>();//正对角线集
        Set<Integer> diag2 = new HashSet<>();//反对角线集
        backtrack(res, queues, n, 0, cols, diag1, diag2);
        return res;
    }

    public static void backtrack(List<List<String>> res, int[] queues, int n, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
        if (row == n) {
            List<String> board = generateBoard(queues, n);
            res.add(board);
        } else {
            //i = 0表示皇后从0开始的位置，逐级遍历
            for (int i = 0; i < n; i++) {
                if (cols.contains(i)) {
                    continue;
                }
                int diagona11 = row - i;
                if (diag1.contains(diagona11)) {
                    continue;
                }
                int diagona12 = row + i;
                if (diag2.contains(diagona12)) {
                    continue;
                }
                queues[row] = i;
                cols.add(i);
                diag1.add(diagona11);
                diag2.add(diagona12);
                backtrack(res, queues, n, row + 1, cols, diag1, diag2);
                //恢复现场
                queues[row] = -1;
                cols.remove(i);
                diag1.remove(diagona11);
                diag2.remove(diagona12);
            }
        }
    }

    public static List<String> generateBoard(int[] queues, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queues[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }


//    public static boolean isValid(int[] record, int i, int j) {
//        for (int k = 0; k < i; k++) {
//            //Math.abs(record[k]-j)==Math.abs(i-k)  这个就是判断 是否斜线
//            if (j == record[k] || Math.abs(record[k]-j)==Math.abs(i-k)){
//                return false;
//            }
//        }
//        return true;
//    }

    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(4);
        System.out.println(lists);
    }

    List<List<String>> res;

    public List<List<String>> solveNQueens1(int n) {
        res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        //创建棋盘board，dfs从 第一行开始遍历
        dfs(board, 0, n);
        return res;
    }

    //dfs遍历每一行，其中的for循环遍历每一列
    public void dfs(char[][] board, int r, int n) {
        if (r == n) {
            res.add(toList(board));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(board, r, i, n)) {
                board[r][i] = 'Q';
                dfs(board, r + 1, n);
                board[r][i] = '.';
            }
        }
    }

    //检查某一点 (r,c) 能否放皇后
    public boolean isValid(char[][] board, int r, int c, int n) {
        //检查该列
        for (int i = 0; i < n; i++) {
            if (board[i][c] == 'Q') {
                return false;
            }
        }
        //检查左上45
        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        //检查右上45
        for (int i = r - 1, j = c + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    //将 char[][] board 转换为 List<String>
    public List<String> toList(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] chars : board) {
            list.add(String.valueOf(chars));
        }
        return list;
    }
}
